﻿// 0904train02.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <unordered_map>
#include <unordered_set>

using namespace std;

/*
 书籍的长、宽都是整数对应(l,w)
 如果书A的长宽度都比B长宽大时，则允许将B排列放在A上面
现在有一组书籍，书籍叠放时要求书籍不能做旋转，请计算最多能有多少个书籍能叠放在一起

输入描述
输入：books = 20,16,15,11,10,10,9,10
说明：总共4本书籍，
第一本长度为20，宽度为16；
第二本书长度为15宽度为11；
依次类推，最后一本书长度为9，宽度为10

输出描述
输出：3
最多能有多少个规格书籍能叠放在一起

输入
20,16,15,11,10,10,9,10
输出
3
最多3个规格的书籍可以叠放到一起，从下到上依次为: [20,16],[15,11],[10,10]
 */
class Solution01
{
public:
    Solution01(vector<vector<int>>&num_vec)
    {
        //最长递增子序列怎么做
        //if(num_vec[i]>num_vec[start])dp[i]=max(dp[i], dp[start]+1)
        //A的长宽度都比B长宽大
        sort(num_vec.begin(), num_vec.end(), [](vector<int>&a, vector<int>&b)
        {
	        if (a[0]==b[0])
	        {
                return a[1] > b[1];
	        }
            return a[0] < b[0];
        });

        vector<int>dynamic_vec(num_vec.size(), 1);

        //vector<vector<int>> 0l 1w

        for (int i=1; i<num_vec.size(); i++)
        {
            for (int start=0; start<i; start++)
            {
	            if (num_vec[start][1]< num_vec[i][1])
	            {
                    dynamic_vec[i] = max(dynamic_vec[i], dynamic_vec[start] + 1);
	            }
            }
        }

        int result = 0;
        for (int i=0; i<dynamic_vec.size(); i++)
        {
            result = max(result, dynamic_vec[i]);
        }
        cout << result;
	    //Solution01
    }
};

/*
 由于演出分布在不同的演出场地，所以连续观看的演出最少有 15 分钟的时间间隔
 小明是一个狂热的文艺迷，想观看尽可能多的演出
 现给出演出时间表，请帮小明计算他最多能观看几场演出

输入
第一行为一个数 N，表示演出场数，1 <= N <= 1000。
接下来 N 行，每行两个空格分割的整数
第一个整数 T 表示演出的开始时间，第二个整数 L 表示演出的持续时间，T 和 L 的单位为分钟，0 <= T <= 1440, 0 < L <= 100。
输出
最多能观看的演出场数。

输入
4
10 20
100 20
150 60
80 40
输出
3
 */
class Solution02
{
public:
    Solution02(vector<vector<int>>&num_vec)
    {
        vector<int>dynamic_vec(num_vec.size(),1);
        sort(num_vec.begin(), num_vec.end(), [](vector<int>&a, vector<int>&b)
        {
            if (a[0] == b[0])
                return a[1] < b[1];
            return a[0] < b[0];
        });

        //if(num_vec[i][0]<=num_vec[start][1]
        for (int i=1; i<num_vec.size(); i++)
        {
            for (int start=0; start<i; start++)
            {
	            if (num_vec[i][0]>=num_vec[start][1])
	            {
                    dynamic_vec[i] = max(dynamic_vec[i], dynamic_vec[start] + 1);
	            }
            }
        }

        int result = 0;
        for (auto&dp_count:dynamic_vec)
        {
            result = max(result, dp_count);
        }
        cout << result;
	    //Solution02
    }
};


/*
找出重复的代码
重复代码查找方法：以字符串形式给出两行代码text1，text2（字符串长度1 < len(text1)，
len(text2) <= 100，由英文字母、数字和空格组成），找出两行代码中的最长公共子串
如果不存在公共子串，返回空字符串
注意子串是连续的

输入
输入的参数text1，text2分别表示两行代码
输出
输出任一最长公共子串

输入
hello123world
hello123abc4
输出
hello123
 */
class Solution03
{
public:
    Solution03(string& text1, string& text2)
    {
        //if(text1[i]==text2[j])
        //dp[r][c]=dp[r-1][c-1]+1
        //记一下result, int common_end_1, int common_end_2

        int row_size = text1.size()+1;
        int col_size = text2.size()+1;

        vector<vector<int>>dynamic_vec(row_size, vector<int>(col_size));

        int max_length = 0, common_end_1 = -1, common_end_2 = -1;
        for (int r=1; r<row_size; r++)
        {
	        for (int c=1; c<col_size; c++)
	        {
                if (text1[r-1]==text2[c-1])
                {
                    dynamic_vec[r][c] = dynamic_vec[r - 1][c - 1] + 1;
                    if (dynamic_vec[r][c]> max_length)
                    {
                        max_length = dynamic_vec[r][c];
                        common_end_1 = r;
                        common_end_2 = c;
                    }
                }

	        }
        }

        if (max_length ==0)
        {
            cout << "";
            return;
        }

        string common_str = text1.substr(common_end_1 - max_length, max_length);
        cout << common_str;
        //Solution03
    }
};

/*
 number 种商品，由于仓库限制每件商品的最大持有数量是 item[index]
 每种商品的价格在每天是 item_price[item_index][day]
 通过对商品的买进和卖出获取利润，请给出商人在 days 天内能获取到的最大的利润
注： 同一件商品可以反复买进和卖出

输入
3     // 输入商品的数量 number
3     // 输入商人售货天数 days
4 5 6 // 输入仓库限制每件商品的最大持有数量是 item[index]
1 2 3 // 输入第一件商品每天的价格
4 3 2 // 输入第二件商品每天的价格
1 5 3 // 输入第三件商品每天的价格
输出
32
 */
class Solution04
{
public:
    Solution04(vector<int>&count_vec,vector<vector<int>>&price_vec)
    {
        //股票dp方程
        //[i][k][0]=max([i-1][k][0],[i-1][k][1]+price_vec[k][i])
        //[i][k][1]=max([i-1][k][1],[i-1][k][0]-price_vec[k][i])
        //[days][k][0]每一层都加一下

        int amount = price_vec.size();//商品数量
        int days = price_vec[0].size(); //天数

        vector<int>status_v(2);
        vector<vector<vector<int>>>dynamic_vec(days, vector<vector<int>>(amount, status_v));

        //[0][k][0]全部为0 [0][k][1] -price_vec[k][0]
        //初始化i=0的状态
        for (int k=0; k<amount; k++)
        {
            dynamic_vec[0][k][0] = 0;
            dynamic_vec[0][k][1] = -price_vec[k][0];
        }

        for (int i=1; i<days; i++)
        {
            for (int k=0; k<amount; k++)
            {
                //昨天没有0，昨天有1，今天卖出
                int inherit_0 = dynamic_vec[i-1][k][0];
                int sale_0 = dynamic_vec[i - 1][k][1] + price_vec[k][i];
                dynamic_vec[i][k][0] = max(inherit_0, sale_0);

                //昨天有1，昨天没有0，今天买入
                int inherit_1 = dynamic_vec[i - 1][k][1];
                int buy1 = dynamic_vec[i - 1][k][0] - price_vec[k][i];
                dynamic_vec[i][k][1] = max(inherit_1, buy1);
            }
        }

        int result = 0;
        for (int k=0; k<amount; k++)
        {
            result += count_vec[k] * dynamic_vec[days - 1][k][0];
        }
        cout << result;
        //Solution04
    }
};

int main()
{
    {
/*
3     // 输入商品的数量 number
3     // 输入商人售货天数 days
4 5 6 // 输入仓库限制每件商品的最大持有数量是 item[index]
1 2 3 // 输入第一件商品每天的价格
4 3 2 // 输入第二件商品每天的价格
1 5 3 // 输入第三件商品每天的价格

3    
3     
4 5 6
1 2 3
4 3 2
1 5 3
*/
        int amount, days;
        cin >> amount >> days;

        vector<int>count_vec(amount);
        for (int i=0; i<amount; i++)
        {
            cin >> count_vec[i];
        }

        vector<vector<int>>price_vec(amount,vector<int>(days));
        for (int k=0; k< amount; k++)
        {
            for (int d=0; d<days; d++)
            {
                cin >> price_vec[k][d];
            }
        }

        Solution04 solu(count_vec, price_vec);
        return 0;
    }
	{
/*
hello123world
hello123abc4
*/
        //string text1 = "hello123world", text2 = "hello123abc4";
        string text1, text2;
        cin >> text1 >> text2;

        Solution03 solu(text1, text2);

        return 0;
	}
    {
/*
4
10 20
100 20
150 60
80 40
*/
        int v_size;
        cin >> v_size;
        cin.ignore();

        vector<string>str_vec;
        for (int i=0; i<v_size; i++)
        {
            string input;
            getline(cin, input);
            str_vec.push_back(input);
        }

        vector<vector<int>>num_vec;
        for (auto&oh_str:str_vec)
        {
            vector<int>min_vec;
            stringstream oh_sstream(oh_str);
            string token;
            while (oh_sstream>>token)
            {
                min_vec.push_back(stoi(token));
            }
            min_vec[1] = min_vec[0] + min_vec[1] + 15;
            num_vec.push_back(min_vec);
        }

        Solution02 solu(num_vec);

        return 0;
    }
    //20,16,15,11,10,10,9,10
    string input;
    getline(cin, input);
    stringstream oh_sstream(input);
    vector<int>origin_vec;
    string token;
    while (getline(oh_sstream,token, ','))
    {
        origin_vec.push_back(stoi(token));
    }

    vector<vector<int>>num_vec;
    for (int i=0; i<origin_vec.size(); i+=2)
    {
        vector<int>min_vec = { origin_vec[i], origin_vec[i+1] };
        num_vec.push_back(min_vec);
    }
    
    Solution01 solu(num_vec);
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
